/*************************************************************************
	> File Name: HuffmanCode.cpp
	> Author: 
	> Mail: 
	> Created Time: 一 10/26 17:53:01 2015
 ************************************************************************/

#include<iostream>
#include<cstdint>
#include<cstdio>

using namespace std;

typedef struct {
    uint16_t weight;
    uint16_t parent, lchild, rchild;
} HNode, *HTree;

typedef char** HCode;
#define INFINITE 10000
//选择父节点为0的最小权值的两个节点
void SelectTwoMini(HTree &HT, int n, int &s1, int &s2) {
    s1 = 0;
    s2 = 0;
    for (int i = 1; i <= n; ++i) {
        if (HT[i].parent == 0 && HT[s1].weight > HT[i].weight)
            s1 = i;
        else {
            if (HT[i].parent == 0 && HT[s2].weight > HT[i].weight)
                s2 = i;
        }
    }
}
//w为n个节点的权值数组
void HuffmanCoding(HTree &HT, HCode &HC, int *w, int n) {
    if (n <= 1)
        return;
    int m = 2 * n - 1;  //total number of nodes
    HT = (HTree) malloc((m + 1) * sizeof(HNode));
    HT[0].weight = INFINITE;
    HTree p;
    int aa;
    for (p = HT + 1, aa = 1; aa <= n; ++p, ++aa) {
        p->weight = w[aa];
        p->parent = 0;
        p->lchild = 0;
        p->rchild = 0;
    }
    for (int i = n + 1; i <= m; ++p, ++i) {
        p->weight = 0;
        p->parent = 0;
        p->lchild = 0;
        p->rchild = 0;
    }
    int s1, s2;  //the index of two minimal weight
    for (int i = n + 1; i <= m; ++i) {
        SelectTwoMini(HT, i - 1, s1, s2);
        HT[s1].parent = i;
        HT[s2].parent = i;
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
    //从叶子节点到根节点逆序求编码
    HC = (HCode)malloc((n + 1) * sizeof(char *));
    char *cd = (char *)malloc(n * sizeof(char));
    cd[n-1] = '\0';
    int f, c;
    for (int i = 1; i <= n; ++i) {
        
        int end = n - 1;  //the end of code
        for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent) {
            if (HT[f].lchild == c)
                cd[--end] = '0';
            else 
                cd[--end] = '1';
        }
        HC[i] = (char *)malloc((n - end) * sizeof(char));
        char *cu = HC[i];
        for (int q = end; q < n; ++q) {
            *cu++ = cd[q];
        }

    }
    free(cd);
    
}

int main(void) {
    cout << "please input the number of code : ";
    int n;
    cin >> n;
    int *w = new int[n + 1];
    cout << "please enter the weight of code : ";
    for (int i = 1; i <= n; ++i)
        cin >> w[i];
    HTree HT;
    HCode HC;
    HuffmanCoding(HT, HC, w, n);
    cout << "the huffman code is:" << endl;
    for (int i = 1; i <= n; ++i) {
        cout << i << "->" << w[i] << " : " << HC[i] << endl;
    }
    return 0;
}
